A lower bound for dilation of an embedding

Title: A lower bound for dilation of an embedding
Creator: Sundara Rajan, R.; Manuel, Paul; Rajasingh, Indra; Parthiban, N.; Miller, Mirka
Relation: The Computer Journal Vol. 58, Issue 12, p. 3271-3278
Publisher Link: http://dx.doi.org/10.1093/comjnl/bxv021
Publisher: Oxford University Press
Resource Type: journal article
Date: 2015
Description: Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. In this paper, we introduce a technique to obtain a lower bound for dilation of an embedding. Moreover, we give algorithms to compute exact dilation of embedding circulant network into a triangular grid, Tower of Hanoi graph and Sierpinski gasket graph, proving that the lower bound obtained is sharp.
Subject: embedding; dilation; circulant network; triangular grid; Tower of Hanoi; Sierpinski gasket graph
Identifier: http://hdl.handle.net/1959.13/1321483
Identifier: uon:24372
Identifier: ISSN:0010-4620
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format